class Solution {
public:
    string reverseWords(string s) {
        removeExtraSpaces(s);

        int left = 0;
        int right = 0;
        for(int i = 0; i <= s.size(); ++i){
            if(i == s.size() || s[i] == ' '){
                
                right = i - 1;
                reverseString(s, left, right);
                left = i + 1;
            }
        }

        reverseString(s , 0, s.size() - 1);

        return s;
    }

    void removeExtraSpaces(string& s) {
        for (int i = s.size() - 1; i > 0; i--) {
            if (s[i] == s[i - 1] && s[i] == ' ') {
                s.erase(s.begin() + i);
            }
        }
        // 删除字符串最后面的空格
        if (s.size() > 0 && s[s.size() - 1] == ' ') {
            s.erase(s.begin() + s.size() - 1);
        }
        // 删除字符串最前面的空格
        if (s.size() > 0 && s[0] == ' ') {
            s.erase(s.begin());
        }
    }

    void reverseString(string &s, int left, int right){
        for(int i = 0; i < (right - left + 1) / 2; ++i) {
            char temp = s[left + i];
            s[left + i] = s[right - i];
            s[right - i] = temp;
        }
    }
};